Коренско дрво
| време | меморија | улаз | излаз |
|---|---|---|---|
| 0,3 s | 64 Mb | стандардни излаз | стандардни улаз |
Повезан граф који садржи \(n\) чворова и \(n-1\) грана се назива дрво. Сваки чвор дрвета може бити његов корен. Напиши програм који за дато дрво и дати корен одређује смер свих грана у том коренском дрвету.
Улаз
Са стандардног улаза се уноси број чворова \(n\) (\(1 \leq n \leq 10^5\)), а затим и опис \(n-1\) грана дрвета. Свака грана је одређена бројевима полазног и завршног чвора (цели бројеви између \(0\) и \(n-1\)), при чему су они задати у произвољном редоследу. У последњем реду се налази редни број корена (број између \(0\) и \(n-1\)).
Излаз
На стандардни излаз треба исписати гране резултујућег коренског дрвета, при чему свака грана треба да буде оријентисана у смеру од корена ка листовима. Низ свих грана (парова бројева) треба да буде лексикографски сортиран (гране се пореде прво по првом, а затим по другом чвору).
Пример 1
Улаз
5 1 0 2 4 3 4 4 1 4
Излаз
1 0 4 1 4 2 4 3
Пример 2
Улаз
5 1 0 2 4 3 4 4 1 2
Излаз
1 0 2 4 4 1 4 3
Објашњење
Морате бити улоговани како бисте послали задатак на евалуацију.